package org.example.everyday;

import java.util.Arrays;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/6/15 9:26
 */
public class Lc719 {
    public static void main(String[] args) {
        Lc719 lc719 = new Lc719();
        int[] nums = {1,3,1};
        int k = 2;
        int res = lc719.smallestDistancePair(nums,k);
        System.out.println(res);
    }

    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, left = 0, right = nums[n - 1] - nums[0];
        while (left <= right){
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                int i = binarySearch(nums,j, nums[j] - mid);
                cnt += j - i;
            }
            if(cnt >= k){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }

    private int binarySearch(int[] nums, int end, int target) {
        int left  = 0,right = end;
        while (left < right){
            int mid = (left + right) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
